/*
 * Copyright (c) 2016- 2020 qolome.com Inc. All Rights Reserved.
 * ProjectName: qolome-knowledge
 * FileName: FibonacciSequence.java
 * Author: jiangfeng@qolome.com
 * Date: 2020/4/26 下午5:34
 * LastModified: 2020/04/02 10:38:02
 */

package com.qolome.knowledge.maths.algorithm;

import java.time.Duration;
import java.time.Instant;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description: 斐波那契数列
 * @author 姜锋
 * @date 2019年3月27日 上午8:31:01
 * @version V1.0
 */
public class FibonacciSequence {
	public static Map<Long, Long> cacheMap = new HashMap<>();
	public static Long f1;
	public static Long f2;

	/**
	 * 
	 * @Description: 根据索引获取值
	 * @author 姜锋
	 * @date 2019年3月27日 上午10:24:25
	 * @param @param index
	 * @param @return
	 * @return Long
	 * @throws
	 */
	public static  Long getNumberOfIndex(Long index) {
		if (index < 3) {
			return 1L;
		} else {
			f1 = cacheMap.get(index - 1);
			if (f1 == null) {
				f1 = getNumberOfIndex(index - 1);
			}
			f2 = cacheMap.get(index - 2);
			if (f2 == null) {
				f2 = getNumberOfIndex(index - 2);
			}
		}
		Long fn = f1 + f2;
		cacheMap.put(index, fn);
		cacheMap.remove(index - 2);
		return fn;
	}
	// 细节展示
	public static void showInfo(Long b) {
		Instant start = Instant.now();
		Long index = getNumberOfIndex(b);
		Instant end = Instant.now();
		System.out
				.println("输出index:" + b + ",所在数: " + index + "耗时毫秒:" + Duration.between(start, end).toMillis() + "毫秒");
	}
	public static void main(String[] args) {
		
		Instant start = Instant.now();
		for (int i = 1; i < 56; i++) {
			showInfo(Long.valueOf(i));
			System.out.println("查询Map长度" + cacheMap.size());
		}
		Instant end = Instant.now();
		System.out.println("计算总耗时"+Duration.between(start, end).toMillis() + "毫秒");
	}
}
